/**
题目:
    给出一个完全二叉树，求出该树的节点个数。
    说明：
    完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
    若最底层为第 h 层，则该层包含 1~ 2h 个节点。
    示例:

    输入: 
        1
    / \
    2   3
    / \  /
    4  5 6

    输出: 6

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/count-complete-tree-nodes
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路:   
    二分搜索
*/
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func countNodes(root *TreeNode) int {
   if root == nil{
       return 0
   }
   d, cur := 0, root
   for cur.Left != nil{
       cur = cur.Left
       d++
   }
   if d  == 0{
       return 1
   }
   left, right := 1, int(math.Pow(2.0,float64(d)) - 1)
   for left <= right{
       mid := left + (right - left) / 2
       if exist(root,mid,d){
           left = mid + 1
       }else{
           right = mid - 1
       }
   }
   return int(math.Pow(2.0,float64(d)) - 1) + left
}

func exist(root *TreeNode, idx, d int)bool{
   l, r := 0, int(math.Pow(2.0,float64(d)) - 1) - 1
   for i := 0; i < d; i++{
       mid := l + (r - l)/2
       if mid >= idx{
           r = mid
           root = root.Left
       }else{
           l = mid + 1
           root = root.Right
       }
   }
    return root != nil
}